#include<iostream>
#include <chrono>
#include <vector>
using namespace std;

class MatrixProcessing {
private:
    int n;
    vector<vector<int>> R;
    vector<vector<int>> E;
    vector<int> lp;

    // 计算每行E矩阵中的最后一个非零元素的位置
    void calculateLP() {
        for (int i = 0; i < m; i++) {
            int x = n - 1;
            int count = 0;
            while (!E[i][count]) {
                x--;
                count++;
            }
            lp[i] = x;
        }
    }

    // 消除E矩阵中的非零元素
    void eliminate() {
        for (int i = 0; i < m; i++) {
            int IsNull = 0;
            for (int j = 0; j < n; j++)
                IsNull = IsNull | E[i][j];
            while (IsNull) {
                int IsNull2 = 0;
                for (int j = 0; j < n; j++)
                    IsNull2 = IsNull2 | R[lp[i]][j];
                if (IsNull2) {
                    int FirstNum = lp[i];
                    for (int j = 0; j < n; j++)
                        E[i][j] = E[i][j] ^ R[FirstNum][j];
                } else {
                    int FirstNum = lp[i];
                    for (int j = 0; j < n; j++) {
                        R[FirstNum][j] = E[i][j];
                        E[i][j] = 0;
                    }
                    break;
                }
                IsNull = 0;
                for (int j = 0; j < n; j++)
                    IsNull = IsNull | E[i][j];
            }
        }
    }

public:
    MatrixProcessing(int size, int density, int percent) : n(size), R(size, vector<int>(size, 0)), E(density, vector<int>(size, 0)), lp(density, 0) {
        for (int i = 0; i < density; i++)
            for (int j = n - percent; j < n; j++)
                E[i][j] = 1;
        for (int i = 0; i < percent; i++)
            R[i][n - i - 1] = 1;
    }

    // 进行矩阵处理并计时
    void processMatrix() {
        auto t1 = chrono::high_resolution_clock::now();
        calculateLP();
        eliminate();
        auto t2 = chrono::high_resolution_clock::now();
        chrono::duration<double, std::milli> fp_ms = t2 - t1;
        cout << "Time taken: " << fp_ms.count() / 1000.0 << "s" << endl;
    }
};

int main() {
    const int n[10] = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000};
    const int m[10] = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000};
    const int p[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

    for (int k = 0; k < 10; k++) {
        cout << k + 1 << "00: ";
        MatrixProcessing mp(n[k], m[k], p[k]);
        mp.processMatrix();
    }

    return 0;
}
